// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const int N = 2e6+50;

char s[N];

int n;
int a[N];

int RL[N];
void manacher(int* a, int n) { // "abc" => "#a#b#a#"
    int r = 0, p = 0;
    for (int i=0; i<n; ++i) {
        if (i < r) RL[i] = min(RL[2 * p - i], r - i);
        else RL[i] = 1;
        while (i - RL[i] >= 0 && i + RL[i] < n && a[i - RL[i]] == a[i + RL[i]])
            RL[i]++;
        if (RL[i] + i - 1 > r) { r = RL[i] + i - 1; p = i; }
    }
    for (int i=0; i<n; ++i) --RL[i];
}

int main(int argc, char const *argv[]) {
    // code
    int t;
    scanf("%d", &t);
    for (int kk=0; kk<t; ++kk) {
        scanf("%s", s);
        n = strlen(s);
        int m = 0;
        for (int i=0; i<n; ++i) {
            a[m++] = '#';
            a[m++] = s[i];
        }
        a[m++] = '#';
        manacher(a, m);

        // for (int i=0; i<m; ++i)
        //     dbg(i, RL[i]);

        int maxp = 0;
        for (int i=0; i<n/2; ++i) {
            if (s[i] == s[n-i-1]) {
                ++maxp;
            } else
                break;
        }
        int ans = 0;
        pair<int, int> l, r;
        for (int i=0; i<m; ++i) {
            int p = (i - RL[i]) / 2;
            if (p <= maxp && i + RL[i] <= m - 2 * p) {
                // dbg(i, RL[i], p);
                if (RL[i] + p * 2 > ans) {
                    ans = RL[i] + p * 2;
                    l = make_pair(0, i + RL[i]);
                    r = make_pair(m - p * 2, m);
                }
            }

            p = (m - i - RL[i])/2;
            // dbg(i, p, RL[i]);
            if (p <= maxp && i - RL[i] >= 2*p) {
                if (RL[i] + p * 2 > ans ) {
                    ans = RL[i] + p * 2;
                    // pos = i;
                    l = make_pair(0, p * 2);
                    r = make_pair(i - RL[i], m);
                }
            }

        }
        // dbg(l.first, l.second, r.first, r.second);

        for (int i=l.first; i<l.second; ++i)
            if (a[i] != '#') putchar(a[i]);
        for (int i=r.first; i<r.second; ++i)
            if (a[i] != '#') putchar(a[i]);
        putchar('\n');


        // printf("%d\n", ans);
    }
    return 0;
}
